#!/usr/bin/python
#coding:utf-8
#加密:c=pow(m,e,n1)   本题是:c=pow(ms[i],ns[i],ns[i])
#e就是ns[i]

import gmpy2
from primefac import gcd
from Crypto.Util.number import long_to_bytes

cs = [0] * 4
ns = [0] * 4

cs[0]=0x76eca2527d6e01a8847ccc58080680f687d4fed686afda4a85d2bebba36475473e027a861abe0ffd3ef7fdf37c4bf86821c64b0544cb9ecfb0d0dced015928ee59ac099711b2ece57a56506a151785ddfd3806d4189212502662e55ebd09a423ed6c0d0b290cecc048d94a275e076f3158a2382d84556222e5daff33860b3379a972404ae677021943c6ef985b937ba096039a67b57abb022e9971c48f608db2d8d7f83bdbccb691dc7bd7fda55689c68cb26bbc88f1ae5f939106b5d5ca8374ff4497380b6e280d4ed16934eb59b148b4831d893966f2bcce601dd1b452f726c487883d1a9b7934bd5b24de4d0f505da81927b809da9c814a0b0b231243008L
ns[0]=0xaeadd829d1588914f40591fe513d59aab4bde65d0862600360cc03160588c64299b46f2d73e4cf92637088dde01bc7044ff5d34cc08fc8e4cf85f83464f4d5e5a28273563834eacc3afe26a5fb7fab13a994a001d7bea49b08cd59eca1707e569cc8c5fc7def9964f1ef45eb5d8acbd391dfbc45fc01876d3a347e5c67a4f69acf842a26f7c128b292f57983d8d25cf0f37f8cd85fd89677ff7b96042c992a528f74826e47066f8d68ce661dafd5392d6339ff792a581703a9a162d6112484bd650f1bbd5699b6db1aaaef43488757238d23a5e8e1fa0cd2694bac14f2cd4b2cbb02778982ff87db99ae7acb86e8361d09bf3e5cbca0ad3237d071b36a954d7L

cs[1]=0x208f0f20588d9fbdee91cab1bf8343c4b44385f52c4c4237e4a08ebba508d0b149748e0f35e0e9a67af6dffb2a54edf8993160f087ab6e2b3843ee690a0f991cf6b221a898598407ac3be9a54ecb100c462490c157d98c4babdb76ad0a00cb45bd064af38fd1006edbfc180b7aa9dec5c988561822b89fc3764f70e59ea5e06c59828fc5f856a340ea6789298b94adb03122029860761258c4b83b3b86310e1536116146604f699fca51bad0108d9e689dfc90d66783432e1a89d8f5fcca2b1a1e5220d1367738f78a5cf09869aa4589fc858e353cd699fb30111283a08e4056a2c47f1ab5bdb420687a6b8ae745db23b17c54b0b2cc36f779b875127da8770L
ns[1]=0x1dfc4df7632253011653013325edafba6a93fbb1f17f886a533c2e1aab4459c1734938dda98a7e575d08afcec466268cdccfecd1ed7564aaf3201d66d1a54af2b1eb985b56c08482a526357199739ccd36f883fc3e1b9bca162d9abd8fb4d06003e258b4c87fd54cdbfd48f19a3a17828d0d72fdda7e05b8adce60c711781598f1569ae281f42b9f2dc1e3fc3a9a53107f0389f36e618d78b4e82473af1922b0c5609c9ab9e960de01c0310c015d7656c8d39efc313b839dedbad68e6a9e43864e9245c75f9b3db34f41fd4e102e25b915460b7ea9a2f285ce8682a1fe21690c78a77ff5370d7bcfafe8033fc485d28d1ea5e9d5c8c00258fe7c85808d224bc9L

cs[2]=0x8a44960619014160cfaee133e85c915466085e3325f3ee10fbeb79369e393413cdd2ced7ff42bdb1201e70effd6e7df7088c7402f13a23d5862b29b1429c8647bd155088f62c937f488c3ea926c59e78e129542bf6740f1ccb06ec25947fbd78da2c783c2fd75416cbd6bb199d34528718934f236a6b94b0b96b4be4814092dff585709cbd6f09bace05a219f72dd7e145db85219b748cf2b00cca2b09559457fcd8f8e434f909b77df0daeadb2cfd09814dd995941009749883a2720eead3ea6a9e5ca83b540bf3d0299f4a2cea8c191dbb5b4ba7760afb1b3935f1985890ff4704a06a3154d85f6b5fb20172a2e1d3a28d322fdec9da888c763585821f53L
ns[2]=0x174daef4510f402863afbbfa68d3563190a2afafd5e519caa941bede4dd7d61c1cfd674ef341cb844e197b0cb63cc4bd37170648867496dbc2ca33537d2bd7b8196adc1d08aa7f017bc77f36698c23827ff73e3e1e8486a65b75b28d0f8dbc23c13bca163f246aaacf983140664b9fdba359186319a50f52215a9cff28655d96225044ca6e5766f1b894bf9ff7c0c58f776215ba95764d80b1630aafb62d1360ddabeba953c9d4b22b4a83a8d6d9c176c09b0577fcba9f15c36b68694feb2e155e85ffc0ecf65ca62e218a95a28ffcb06480f170ead7fbde96cd5a8e3b66e764d1b5f8fe22092e94273aac13972155ec0985d00c10aebd49ea4fbcc9a9985b7L

cs[3]=0x13b5d93d7de2abd0a2beec3789028a258412d71a8984e9013e52c417ae8fdc92f2f0b6763360dcef88c3b9a535bdb582e307339fe55615097900fcc58d1ac66de5cde01d94f6dee2a95ddf1009b320ccd2a6beb4d77fe5fa367ef956454747057fcdca0cd39ed1e0fe11b766a8c705640f2149e3d86938c78cfacc3f0e3075ffa758bacf0c58d5ea659dc4439a2f16a732a51be0d4f3c920789cbf20ca01d6cd77ca2934064fb508387c1bd2e55dd7c92a45be117a9c32ad992d2e51fb8e730d150a4520dbfd177f2a77e5856039c125a7142d77c732cdb26f0f731cc136d6cee4465e1654bb94a5ec36e91c4f277d68ba8d06b9aea8834e61bb29aca252a7fL
ns[3]=0x501011a69b682f904e7b730857e6792d9f422d0df83f284e58311d5e9994e64a259efbb0ee2c4b42fb90b1d934dc482a88c7c186dab0bbd867758b88c3a14ccb2e061556b1821033917cdc7c27c1ab020f8fcd7766eb58e85fd364b179997ec830ad2b44a0d87955aef698039b9e9680bc37c7f9c55e44b334784910a509db1d8637258d709f6fae43436af65c9656a7d48a66d341143f8198e2c16d9f1abf544cc8bd5828047f0d63c39db60e68fe27a7ae33106b5571a2c2943146bbe0c649ef290cd8319aa4ccce7a7bf114f2d67237a60c0934b4cedbc30022f6d1f863643136baebd81037dd71f38b5b0c6c3d48718187db64eb17c20bd95b85aa6de83L

n1 = ns[0]
c1 = cs[0]
n2 = ns[1]
c2 = cs[1]
n3 = ns[2]
c3 = cs[2]
n4 = ns[3]
c4 = cs[3]


n1p1 = gcd(n1,n2)                
n1p2 = gcd(n1,n3)                       
n1p3 = gcd(n1,n4)                         
n1p4 = n1/(n1p1*n1p2*n1p3)                       
phi1 = (n1p1-1)*(n1p2-1)*(n1p3-1)*(n1p4-1)
                     

n2p1 = gcd(n2,n1)
n2p2 = gcd(n2,n3)
n2p3 = gcd(n2,n4)
n2p4 = n2/(n2p1*n2p2*n2p3)  
phi2 = (n2p1-1)*(n2p2-1)*(n2p3-1)*(n2p4-1)


n3p1 = gcd(n3,n1)                
n3p2 = gcd(n3,n2)                      
n3p3 = gcd(n3,n4)                        
n3p4 = n3/(n3p1*n3p2*n3p3)                                            
phi3 = (n3p1-1)*(n3p2-1)*(n3p3-1)*(n3p4-1)


n4p1 = gcd(n4,n1)
n4p2 = gcd(n4,n2) 
n4p3 = gcd(n4,n3) 
n4p4 = n4/(n4p1*n4p2*n4p3)  
phi4 = (n4p1-1)*(n4p2-1)*(n4p3-1)*(n4p4-1)
 

d1 = gmpy2.invert(n1,phi1)   
d2 = gmpy2.invert(n2,phi2)
d3 = gmpy2.invert(n3,phi3)
d4 = gmpy2.invert(n4,phi4)

m1 = pow(c1,d1,n1)
m2 = pow(c2,d2,n2)
m3 = pow(c3,d3,n3)
m4 = pow(c4,d4,n4)

print hex(m1)
print hex(m2)
print hex(m3)
print hex(m4)

#nc传过去m1,m2,m3,m4就可得到flag
# flag{H0W_c1EV3R_Y0u_AR3_C0ngRatu1at10n5}
